/*
给定一个由 '1'（陆地）和 '0'（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。

示例 1:

输入:
11110
11010
11000
00000

输出: 1
示例 2:

输入:
11000
11000
00100
00011

输出: 3

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/number-of-islands
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/
class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int x_len=grid.size();
        if(x_len==0){
            return 0;
        }
        int y_len=grid[0].size();
        vector<vector<bool>> visited(x_len,vector<bool>(y_len,false));
        vector<vector<int>> direction{{1,0},{-1,0},{0,-1},{0,1}};
        stack<pair<int,int>> dfs;
        int num=0;
        int x=0;
        int y=0;
        int new_x=0;
        int new_y=0;
        bool find_next=false;
        pair<int,int> tmp;
        for(int i=0;i<x_len;i++){
            for(int j=0;j<y_len;j++){
                //cout<<"grid("<<i<<","<<j<<")"<<"="<<grid[i][j]<<",not visited? "<<!visited[i][j]<<endl;
                if((grid[i][j]=='1')&&(!visited[i][j])){
                    dfs.push(make_pair(i,j));
                    visited[i][j]=true;
                    num++;
                    while(!dfs.empty()){
                        tmp=dfs.top();
                        find_next=false;
                        x=tmp.first;
                        y=tmp.second;
                        //cout<<"("<<x<<","<<y<<")"<<endl;
                        for(auto& dir:direction){
                            new_x=x+dir[0];
                            new_y=y+dir[1];
                            if(0<=new_x&&new_x<x_len&&0<=new_y&&new_y<y_len&&grid[new_x][new_y]=='1'&&!visited[new_x][new_y]){
                                //cout<<"in"<<endl;
                                visited[new_x][new_y]=true;
                                dfs.push(make_pair(new_x,new_y));
                                find_next=true;
                            }
                        }
                        if(!find_next){
                            dfs.pop();
                        }
                    }
                }
            }
        }
        return num;
    }
};

//简单算法，统计进行dfs的个数
class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int num=0;
        for(int i=0;i<grid.size();i++){
            for(int j=0;j<grid[0].size();j++){
                if(grid[i][j]>'0'){
                    dfs(grid,i,j);
                    num++;
                }
            }
        }
        return num;
    }
private:
    vector<vector<int>> direction{{1,0},{0,1},{-1,0},{0,-1}};
    void dfs(vector<vector<char>>& grid,int i,int j){
        if(i<0||i>=grid.size()||j<0||j>=grid[0].size()||grid[i][j]=='0'){
            return;
        }
        grid[i][j]='0';
        for(auto& d:direction){
            dfs(grid,i+d[0],j+d[1]);
        }
    }

};